A document search system may index millions of documents associated with a corpus. The index for the search system may be an inverted index that may include posting lists, each posting list representing terms and documents that contain the term. The documents identified in the posting list for a term may be ordered, for example sorted by a document identifier, to assist in locating specific documents within the posting list. In some systems the document identifiers may be assigned based on a rank of the document, so that documents with a higher rank have a lower identifier. The search system may also include other information, such as metadata for the posting lists and documents and/or parsed and encoded document content. In a distributed environment, the index may be divided among various the machines by document, by term, or both. Every day the documents of the corpus may change, and often a document, such as a news organization's home page or a blog, may change several times a day. Re-encoding the posting lists of the index to reflect these changes may be time consuming, but failing to update the index may cause the index to become stale. Appending updates to the end of the posting list can provide an easy and fast method to update the index, but fails to preserve the order of the document identifiers and sacrifices some query optimization techniques, such as the ability to terminate a search early if a minimum number of responsive documents are found.